from leetcode_test import TreeNode
from functools import lru_cache


class Solution:
    def lowestCommonAncestor(
        self, root: "TreeNode", p: "TreeNode", q: "TreeNode"
    ) -> "TreeNode":
        @lru_cache(None)
        def find(root, value):
            if not root:
                return False
            if root.val == value:
                return True

            return find(root.left, value) or find(root.right, value)

        def helper(root):
            if not root:
                return

            if find(root.left, p.val) and find(root.left, q.val):
                return helper(root.left)
            elif find(root.right, q.val) and find(root.right, p.val):
                return helper(root.right)
            else:
                return root

        return helper(root)


def test():
    t = TreeNode.create([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
    p = TreeNode.create([5])
    q = TreeNode.create([1])
    solution = Solution().lowestCommonAncestor(t, p, q)
    assert solution.val == 3


def test1():
    t = TreeNode.create([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
    p = TreeNode.create([5])
    q = TreeNode.create([4])
    solution = Solution().lowestCommonAncestor(t, p, q)
    assert solution.val == 5

def test2():
    t = TreeNode.create([37,-34,-48,None,-100,-101,48,None,None,None,None,-54,None,-71,-22,None,None,None,8])
    p = TreeNode.create([-71])
    q = TreeNode.create([48])
    solution = Solution().lowestCommonAncestor(t, p, q)
    assert solution.val == 48

def test3():
    t = TreeNode.create([37,-34,-48,None,-100,-101,48,None,None,None,None,-54,None,-71,-22,None,None,None,8])
    p = TreeNode.create([37])
    q = TreeNode.create([8])
    solution = Solution().lowestCommonAncestor(t, p, q)
    assert solution.val == 37

if __name__ == "__main__":
    t = TreeNode.create([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
    p = TreeNode.create([5])
    q = TreeNode.create([4])

    print(Solution().lowestCommonAncestor(t, p, q))
